前一个和式可以计算,不再赘述,考虑后一个和式。
我们知道:
对于每一个 用单调栈找到左右比它小的第一个元素的位置即可。
注意有一边严格小,另一边不大于,这样才不会重复遗漏。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
const int MAXN = 5e5;
int rk[ MAXN + 5 ] , sa[ MAXN + 5 ] , ht[ MAXN + 5 ];
int tmp[ MAXN + 5 ] , buc[ MAXN + 5 ];
void SA( int len , char *str ) {
int s = 256;
for( int i = 1 ; i <= s ; i ++ ) buc[ i ] = 0;
for( int i = 1 ; i <= len ; i ++ ) buc[ rk[ i ] = str[ i ] ] ++;
for( int i = 1 ; i <= s ; i ++ ) buc[ i ] += buc[ i - 1 ];
for( int i = len ; i >= 1 ; i -- ) sa[ buc[ rk[ i ] ] -- ] = i;
for( int w = 1 ; w <= len ; w <<= 1 ) {
int cnt = 0;
for( int i = len - w + 1 ; i <= len ; i ++ ) tmp[ ++ cnt ] = i;
for( int i = 1 ; i <= len ; i ++ ) if( sa[ i ] > w ) tmp[ ++ cnt ] = sa[ i ] - w;
for( int i = 1 ; i <= s ; i ++ ) buc[ i ] = 0;
for( int i = 1 ; i <= len ; i ++ ) buc[ rk[ i ] ] ++;
for( int i = 1 ; i <= s ; i ++ ) buc[ i ] += buc[ i - 1 ];
for( int i = len ; i >= 1 ; i -- ) sa[ buc[ rk[ tmp[ i ] ] ] -- ] = tmp[ i ] , tmp[ i ] = 0;
swap( tmp , rk );
rk[ sa[ 1 ] ] = cnt = 1;
for( int i = 2 ; i <= len ; i ++ ) rk[ sa[ i ] ] = ( tmp[ sa[ i ] ] == tmp[ sa[ i - 1 ] ] && tmp[ sa[ i ] + w ] == tmp[ sa[ i - 1 ] + w ] ) ? cnt : ++ cnt;
if( cnt == len ) break; s = cnt;
}
for( int i = 1 , k = 0 ; i <= len ; i ++ ) {
if( k ) k --;
while( str[ sa[ rk[ i ] ] + k ] == str[ sa[ rk[ i ] - 1 ] + k ] ) k ++;
ht[ rk[ i ] ] = k;
}
}
int n; char str[ MAXN + 5 ];
int top , stk[ MAXN + 5 ] , l[ MAXN + 5 ] , r[ MAXN + 5 ];
LL Ans;
int main( ) {
scanf("%s", str + 1 ); n = strlen( str + 1 );
SA( n , str );
// for( int i = 1 ; i <= n ; i ++ ) printf("%d%c", ht[ i ] , i == n ? '\n' : ' ' );
ht[ stk[ top = 1 ] = 0 ] = -1;
for( int i = 1 ; i <= n ; i ++ ) {
while( top && ht[ i ] < ht[ stk[ top ] ] ) top --;
l[ i ] = stk[ top ]; stk[ ++ top ] = i;
}
ht[ stk[ top = 1 ] = n + 1 ] = -1;
for( int i = n ; i >= 1 ; i -- ) {
while( top && ht[ i ] <= ht[ stk[ top ] ] ) top --;
r[ i ] = stk[ top ]; stk[ ++ top ] = i;
}
// for( int i = 1 ; i <= n ; i ++ ) printf("%d %d\n", l[ i ] , r[ i ] );
for( int i = 1 ; i <= n ; i ++ ) Ans -= 2ll * ht[ i ] * ( i - l[ i ] ) * ( r[ i ] - i );
for( int i = n ; i >= 2 ; i -- ) Ans += 3ll * ( i - 1 ) * i / 2;
printf("%lld\n", Ans );
return 0;
}
/*
eededeedeedeedde
1798
*/